1. Field of the Invention
The present invention relates to a distributed processing device of a digital filter, and more particularly, to a distributed device having a high data input rate, i.e. sampling frequency, in a digital filter widely used in image processing and the like.
2. Description of the Background Art
The processing content of a two-dimensional digital filter is defined by the following equation (1). ##EQU1##
When a signal data is entered in a raster scan manner, the direction of the raster scan (referred to as "horizontal direction" hereinafter) is represented by z.sub.1, and the direction perpendicular to the raster scan direction (referred to as "vertical direction" hereinafter) is represented by z.sub.2 in the above equation (1). z.sub.1.sup.-1, z.sub.1.sup.-2, . . . , z.sub.1.sup.-m+1 represent delay of order 1, delay of order 2, . . . , delay of order (m-1), respectively, in the horizontal direction. Similarly, z.sub.2.sup.-1, z.sub.2.sup.-2, . . . , z.sub.2.sup.-n+1 represent delay of order 1, delay of order 2, . . . , delay of order (n-1), respectively, in the vertical direction. A matrix [h (i, j)] is a coefficient representing the properties of a two-dimensional filter.
A method of decomposing a multidimensional digital filter into low dimensional digital filters of a multistage separable type is disclosed in "The LU Decomposition Theorem and Its Implications to the Realization of Two-Dimensional Digital Filters", IEEE Transactions on ASSP, 33, No. 3, pp. 694-711 (June 1985) by C. L. Nikias, A. P. Chrysafis, and A. N. Venetsanopoulos.
FIG. 6 shows a structure of a two-dimensional digital filter by LU decomposition. If P is the order (or rank ([h (i, j)]) of a matrix [h (i, j)] of equation (1), the two-dimensional digital filter of FIG. 6 includes P one-dimensional digital filters 1.sub.0, 1.sub.1, 1.sub.2, . . . , 1.sub.(P-1) in the z.sub.1 direction formed of the lower triangular matrix decomposing the matrix [h (i, j)] and P one-dimensional digital filters 2.sub.0, 2.sub.1, 2.sub.2, . . . , 2.sub.(P-1) in the z.sub.2 direction formed of the upper triangular matrix, connected in series. A signal data is entered in parallel to the one-dimensional digital filters 1.sub.0, 1.sub.1, 1.sub.2, . . . , 1.sub.(P-31 1). The outputs thereof are entered to the two-dimensional digital filters 2.sub.0, 2.sub.1, 2.sub.2, . . . , 2.sub.(P-1). The respective outputs are summed up by adders 3.sub.0, 3.sub.1, 3.sub.2, . . . , 3.sub.(P-1) to be output.
LU decomposition is specifically indicated in the following equation (2). ##EQU2##
In the matrix [h (i, j)] representing the properties of a two-dimensional digital filter, elements 363 of the 0 row are triplicities of elements 121, respectively, of the second row. They are dependent and have the rank of 2. Therefore, the elements in the second column in the lower triangular matrix, and the elements in the second row in the upper triangular matrix are all 0. Therefore, the formation of a two-dimensional digital filter as shown in equation (2) according to LU decomposition results in the structure shown in FIG. 7 where two one-dimensional digital filters are connected serially in the horizontal direction and the vertical direction. Referring to FIG. 7, a one-dimensional digital filter 4 has [1, z.sub.1.sup.-1, z.sub.1.sup.-2 ] multiplied by [1, 2, 1], a one-dimensional digital filter 5 has [3, 1, 1] multiplied by [1, z.sub.2.sup.-1, z.sub.2.sup.-2 ], a one-dimensional digital filter 6 has [0, 4, 3] multiplied by [1, z.sub.1.sup.-1, z.sub.1.sup.-2 ], and a one-dimensional digital filter 7 has [0, 1, 0] multiplied by [1, z.sub.2.sup.-1, z.sub.2.sup.-2 ]. The outputs of one-dimensional digital filters 5 and 7 are added in an adder 8, whereby an output is obtained.
FIG. 8 shows a hardware structure based on the block diagram of FIG. 7. Referring to FIG. 8, D represents a delay circuit of the z.sub.1 direction (horizontal direction). It is formed of a data latch, for example, to store one signal data. 1H represents a delay circuit of the z.sub.2 direction (vertical direction). It is formed of a FIFO memory, for example, to store signal data of 1 scan line. The multiplier in one-dimensional digital filter 4 multiplies a coefficient 2 by the output of the delay circuit to calculate 2z.sub.1.sup.-1.
When a two-dimensional digital filter formed by LU decomposition is to be realized on a data driving type processor, the delay circuit D of the horizontal direction can be realized by a generation number operation which is the data identifier in the signal data. The delay circuit 1H of the vertical direction preferably employs an external storage device as a FIFO memory since the amount of data to be stored is great.
FIG. 9 shows a signal processing system using a data driven type processor. Referring to FIG. 9, signal input data sampled in the raster scan direction is input in time series from a data transmission path 27 or 28 to a data driven type processor 21. Data driven type processor 21 has pre-specified procedures stored therein by which processing is carried out. A memory interface 22 receives via a data transmission path 24 an access (reference/update of image memory) request to an image memory 23 from data driven type processor 21. After image memory 23 is accessed via a memory access control line 26, the result is returned to data driven type processor 21 via a data transmission path 25. Following the process of a signal input packet, data driven type processor 21 provides a signal output packet via a data transmission path 29 or 30. Data driven type processor 21 realizes the function of an FIFO memory by writing into image memory 23 input data of the vertical direction delay circuit 1H and reading out the same after elapse of the time of 1 line.
As in the conventional case, a two-dimensional digital filter can be formed with multistages of one-dimensional digital filters connected serially according to LU decomposition. As shown in FIG. 6, assuming that the flow rate (corresponding to sampling frequency) of input data to a two-dimensional digital filter is R, the flow rate of signal data entered to one dimensional digital filters 1.sub.0, 1.sub.1, 1.sub.2, . . . , 1.sub.P-1) of each horizontal direction is R since the input signal data is copied and entered to one dimensional digital filters 1.sub.0, 1.sub.1, 1.sub.2, . . . , 1.sub.(P-1) of the horizontal direction.
Also, because the inputs of one dimensional digital filters 2.sub.0, 2.sub.1, 2.sub.2, . . . 2.sub.P-1) of the vertical direction are connected to the outputs of one dimensional digital filters 1.sub.0, 1.sub.1, 1.sub.2, . . . 1.sub.(P-1) of the horizontal direction, the input flow rate of one-dimensional digital filters 2.sub.0, 2.sub.1, 2.sub.2, . . . 2.sub.(P-1) of the vertical direction is also R. Therefore, the maximum input flow rate acceptable by the two-dimensional digital filter is limited to the lowest acceptable input flow rate of the one dimensional digital filters after decomposition. In the case where discrete processors are assigned to each individual one dimensional digital filter, there was a problem that the entire processing ability was limited by the processor to which the filter having the greatest processing amount is assigned to.